Many present-day Internet Protocol (IP) networks will eventually have to be upgraded to meet future levels of demand for bandwidth capacity. This is true for networks on which MultiProtocol Label Switching has been implemented (“MPLS networks”) as well as for other IP networks.
In some scenarios for upgrading the networks, older links, having relatively low capacity, are replaced by higher-capacity links. In typical scenarios, the new link has four times the carrying capacity of the old link. Such scenarios have drawbacks. One drawback is that it is very expensive to totally replace a link. Another drawback is that in general, the new link will be utilized at a low level of efficiency at the time of upgrade, typically less than 25% efficiency.
Because of these, and other, drawbacks, a second scenario has been considered. The second scenario involves upgrading the links incrementally. That is, capacity is increased between a pair of routers by adding one or more new links in parallel with those that are already installed between the given routers. Such a scenario offers lower cost at each stage of expansion. Such a scenario will also often prolong the useful lifetime of existing routers because it can generally be implemented within the constraints of existing processing speeds.
The practicality of incremental upgrading, at least of MPLS networks, can be enhanced by the practice of link bundling as described, for example, in K. Kompella et al., “Link Bundling in MPLS Traffic Engineering,” Internet Draft <draft-kompella-mpls-bundle-05.txt> (February 2001). In link bundling, the pair of routers is connected by multiple parallel links having the same attributes. The parallel links are treated as a single “bundled link” when routing tables are computed. This can significantly reduce the processing load on the routers that compute the routing tables. The individual links that collectively define the bundled link are referred to as “component links.”
In link bundling, a given Label Switched Path (LSP) cannot be divided among the component links of the bundle. Instead, during setup of an LSP with a given bandwidth reservation B, the corresponding router will search for a component link with unreserved bandwidth greater than B. The router will associate the LSP with one particular such link, if, indeed, such a link can be found. If no component link is found having unreserved bandwidth B, the LSP request will fail.
Although useful, link bundling does not consistently achieve the highest possible utilization of available bandwidth on the bundled link. That is, even if the total unreserved bandwidth on the bundled link exceeds B, the LSP request will fail if the unreserved bandwidth is distributed over two or more component links in parcels that are individually smaller than B. In many such cases, the unreserved bandwidth will go unused and efficiency will suffer.
Thus, there is still a need for a more efficient scheme of link bundling.